#include<vector>
#include<unordered_map>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;

class Solution {
private:
    struct Compare {
        bool operator()(const vector<int>& left, const vector<int>& right) {
            return left[2] > right[2];
        }
    };
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {

        unordered_multimap<int, vector<int>>map;
        for (auto& flight : flights) {
            map.emplace(flight[0], flight);
        }

        //src,K,cost
        priority_queue<vector<int>,vector<vector<int>>, Compare>queue;
        queue.push(vector<int>{src, K, 0});
        int cnt = INT32_MAX;
        while (!queue.empty()) {
            auto vec = queue.top();
            queue.pop();
            if (vec[0] == dst) 
                return vec[2];
            if (vec[1] == -1)
                continue;
            auto range = map.equal_range(vec[0]);
            for (auto it = range.first; it != range.second; ++it) {
                queue.push(vector<int>{it->second[1], vec[1] - 1, vec[2] + it->second[2]});
            }
        }
        return -1;
    }
};

//int main() {
//    vector<vector<int>> flights;;
//    flights.push_back(vector<int>{ 0, 1, 1 });
//    flights.push_back(vector<int>{ 0, 2, 5 });
//    flights.push_back(vector<int>{ 1, 2, 1 });
//    flights.push_back(vector<int>{ 2, 3, 1 });
//    Solution sol;
//    cout<<sol.findCheapestPrice(4, flights, 0, 3, 1);
//}